#include <iostream>
#include <vector>

int get_mid(std::vector<int>& arr,int left,int right){
    int base_num = arr[right];
    int low = left -1;
    for (int i = left;i<right ;i++){
        if(arr[i] < base_num){
            low++;
            std::swap(arr[i],arr[low]);
        } 
    }
    std::swap(arr[low+1],arr[right]);
    return low+1;
}

int insert_sort(std::vector<int> & arr,int left ,int right){
    
    if(left > right){
        return 0;
    }
    int mid = get_mid(arr,left,right);
    insert_sort(arr,left,mid-1);
    insert_sort(arr,mid+1,right);
    return 0;
}

int main(){
    std::cout << "start" <<std::endl;
    std::vector<int> arr = {5,3,1,2,4};
    insert_sort(arr,0,4);
    for(int i =0;i<arr.size();i++){
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}